/**
 * 一棵树，不多于一个值为x的节点
 * 找x的所有所有祖先并打印
 * 采用非递归的后续遍历，当遍历到x节点时栈中所有元素都是这个节点的祖先，依次打印即可
 */

#include "BiTree.h"
typedef struct
{
    BiTree *t;
    int tag; // 0 表示左子树被访问过，1表示右子树备份访问过
} stack;

void search(BiTree *bt, int x)
{
    stack s[1024];
    int top = 0;
    while (bt != nullptr || top > 0) 
    {
        while (bt != nullptr && bt->val != x)// 不断左递归，并将元素入栈
        {
            s[++top].t = bt;
            s[top].tag = 0;
            bt = bt->left;
        }

        if (bt != nullptr && bt->val == x)//找到x，输出祖先，然后结束
        {
            cout << "所有祖先为：\n";
            for (int i = 1; i <= top; i++)
            {
                cout << s[i].t->data;
                return;
            }
        }
        while (top != 0 && s[top].tag == 1)//退栈
        {
            top--;
        }
        if (top != 0)//沿着分支往右下走
        {
            s[top].tag = 1;
            bt = s[top].t->right;
        }
    }
}